// https://www.lintcode.com/problem/combination-sum/

public class Solution {
    /**
     * @param candidates: A list of integers
     * @param target: An integer
     * @return: A list of lists of integers
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // write your code here
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(candidates);
        _combinationSum(ret, new ArrayList<Integer>(), candidates, 0, 0, target);
        return ret;
    }

    protected void _combinationSum(List<List<Integer>> ret,
                                   List<Integer> comb,
                                   int[] candidates,
                                   int idx, int sum,
                                   int target) {
        if (sum == target) {
            List<Integer> r = new ArrayList<>();
            for (Integer i : comb) {
                r.add(i);
            }
            ret.add(r);
        } else if (sum > target) {
            return;
        } else {
            if (idx < candidates.length) {
                comb.add(candidates[idx]);
                _combinationSum(ret, comb, candidates, idx, sum + candidates[idx], target); // 因为可以重复使用，还是从原来的idx继续。
                comb.remove(comb.size() - 1);
                int prev = candidates[idx];
                int j = idx;
                while (j < candidates.length) {
                    if (candidates[j] != prev) {
                        prev = candidates[j];
                        comb.add(candidates[j]);
                        _combinationSum(ret, comb, candidates, j, sum + prev, target);
                        comb.remove(comb.size() - 1);
                    }
                    ++j;
                }
            }
        }
    }
}